Conditionally Cycle-Free Generalized Tanner Graphs: Theory and Application to High-Rate Serially Concatenated Codes

摘要

Generalized Tanner graphs have been implicitly studied by a number of authorsunder the rubric of generalized parity-check matrices. This work considers theconditioning of binary hidden variables in such models in order to break allcycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms.Conditionally cycle-free generalized Tanner graphs are shown to imply optimalSISO decoding algorithms for the first order Reed-Muller codes and their duals- the extended Hamming codes - which are substantially less complex thanconventional bit-level trellis decoding. The study of low-complexity optimalSISO decoding algorithms for the family of extended Hamming codes ispractically motivated. Specifically, it is shown that exended Hamming codesoffer an attractive alternative to high-rate convolutional codes in terms ofboth performance and complexity for use in very high-rate, very low-floor,serially concatenated coding schemes.